package leetcode.code0464;

import leetcode.helper.HelpDebug;

public class Solution1 extends Solution464 {

	@Override
	public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
		int l = 1;
		int r = maxChoosableInteger;
		boolean[] f = new boolean[desiredTotal + 1];
		int t = l + r;
		int p = t;
		f[t] = true;// 后手赢
		boolean head = true;
		r--;
		l++;
		while (p <= desiredTotal) {
			if (head) {
				p = p + r + 1;
				if (p > desiredTotal)
					break;
				f[p] = true;
				head = !head;
				r--;
				t = p + l;
				l--;
			} else {
				if (p < t) {
					f[p] = true;
					p++;
				} else {
					head = !head;
				}
			}
		}
		HelpDebug.print(f);
		return !f[desiredTotal] ? true : false;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
//		boolean b = so.canIWin(4, 6);
//		System.out.println(b);
//		so.debug1();
		so.debug2();
//		so.debug3();
//		so.debug4();
	}

}
